// @algorithm @lc id=820 lang=cpp 
// @title find-eventual-safe-states


#define print(...)
// @test([[1,2],[2,3],[5],[0],[5],[],[]])=[2,4,5,6]
// @test([[1,2,3,4],[1,2],[3,4],[0,4],[]])=[4]
enum State {
    UNKNOWN,
    DANGER,
    SAFE,
};
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> ans;
        vector<State> st(graph.size(), UNKNOWN);

        function<State(int)> dfs = [&](int idx){
            if(UNKNOWN != st[idx]) return st[idx];
            st[idx] = DANGER;
            for(auto i : graph[idx])
                if(SAFE != dfs(i)) return DANGER;
            return st[idx] = SAFE;
        };

        for(int i=0; i<(int)graph.size(); i++)
            if(SAFE == dfs(i)) ans.push_back(i);
        return ans;
    }
};